package com.sheng.leetcode.year2022.month04.day25;

import org.junit.Test;

import java.util.*;

/**
 * @author liusheng
 * @date 2022/04/25
 *
 * 398. 随机数索引
 *
 * 给你一个可能含有 重复元素 的整数数组 nums ，请你随机输出给定的目标数字 target 的索引。
 * 你可以假设给定的数字一定存在于数组中。
 *
 * 实现 Solution 类：
 *
 * Solution(int[] nums) 用数组 nums 初始化对象。
 * int pick(int target) 从 nums 中选出一个满足 nums[i] == target 的随机索引 i 。
 * 如果存在多个有效的索引，则每个索引的返回概率应当相等。
 *
 * 示例：
 *
 * 输入
 * ["Solution", "pick", "pick", "pick"]
 * [[[1, 2, 3, 3, 3]], [3], [1], [3]]
 * 输出
 * [null, 4, 0, 2]
 *
 * 解释
 * Solution solution = new Solution([1, 2, 3, 3, 3]);
 * solution.pick(3); // 随机返回索引 2, 3 或者 4 之一。每个索引的返回概率应该相等。
 * solution.pick(1); // 返回 0 。因为只有 nums[0] 等于 1 。
 * solution.pick(3); // 随机返回索引 2, 3 或者 4 之一。每个索引的返回概率应该相等。
 *
 * 提示：
 *
 * 1 <= nums.length <= 2 * 104
 * -231 <= nums[i] <= 231 - 1
 * target 是 nums 中的一个整数
 * 最多调用 pick 函数 104 次
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/random-pick-index
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0398 {

    @Test
    public void test01(){
        int[] nums = new int[] {1,2,3,3,3};
        Solution solution = new Solution(nums);
        System.out.println(solution.pick(3));
    }
}
class Solution {

    Random random = new Random();
    Map<Integer, List<Integer>> map = new HashMap<>();

    public Solution(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            List<Integer> list = map.getOrDefault(nums[i], new ArrayList<Integer>());
            list.add(i);
            map.put(nums[i], list);
        }
    }

    public int pick(int target) {
        List<Integer> list = map.get(target);
        return list.get(random.nextInt(list.size()));
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int param_1 = obj.pick(target);
 */

//class Solution {
//    Random random = new Random();
//    Map<Integer, List<Integer>> map = new HashMap<>();
//    public Solution(int[] nums) {
//        int n = nums.length;
//        for (int i = 0; i < n; i++) {
//            List<Integer> list = map.getOrDefault(nums[i], new ArrayList<>());
//            list.add(i);
//            map.put(nums[i], list);
//        }
//    }
//    public int pick(int target) {
//        List<Integer> list = map.get(target);
//        return list.get(random.nextInt(list.size()));
//    }
//}
//
//作者：AC_OIer
//链接：https://leetcode-cn.com/problems/random-pick-index/solution/by-ac_oier-zhml/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

//哈希表 预处理（定长数据流）
//切换英文补全一下数据范围：
//
//1 <= nums.length <= 2 * 10^4
//-2^{31} <= nums[i] <= 2^{31} - 1
//target 确保存在于 nums 中
//最多调用 10^4 次的 pick
//为了方便，我们令 nums 的长度为 n，利用 n 的数据范围为 2 * 10^4
// ，且完整的数组为初始化时已给出，我们可以通过使用「哈希表 + 预处理」的方式进行求解。
//具体的，在构造函数传入 nums 时，遍历 nums 并存储每个 nums[i] 对应的下标集合，
//即使用哈希表以 nums[i] 为键，下标集合 List 作为值进行存储。
//在 pick 操作时，通过 O(1) 的复杂度取出所有 nums[i] = target 的集合下标，再随机一个下标进行返回。
//
//作者：AC_OIer
//链接：https://leetcode-cn.com/problems/random-pick-index/solution/by-ac_oier-zhml/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
